package com.yww.leetcode.linkedlist;

import com.yww.leetcode.common.ListNode;

/**
 * @author yww
 * @description 206. 反转链表
 * @since 2024/2/2 10:12
 */
public class ReverseList206 {
    public ListNode reverseList(ListNode head) {
        // 逆
        head = reverseList01(head);
        // 正
        head = reverseList02(head);
        // 逆
        head = reverseList03(head);
        // 正
        head = reverseList04(head);
        // 逆
        head = reverseList05(head);
        return head;
    }

    // 方法1：每次构造新节点
    private static ListNode reverseList01(ListNode o1) {
        ListNode n1 = null;
        ListNode p = o1;
        while (p != null) {
            n1 = new ListNode(p.val, n1);
            p = p.next;
        }
        return n1;
    }

    // 方法2：构造一个外部链表，从旧链表移出头添加新链头（面向对象）
    private static ListNode reverseList02(ListNode o1) {
        LinkedList ol = new LinkedList(o1);
        LinkedList nl = new LinkedList(null);
        ListNode first;
        while ((first = ol.removeFirst()) != null) {
            nl.addFirst(first);
        }
        return nl.head;
    }

    // 方法3：递归，找到最后一个节点，归的时候交互相邻两个节点的次序，并让当前节点：p.next=null。
    private static ListNode reverseList03(ListNode p) {
        // 找到最后一个节点
        if (p == null || p.next == null) {
            return p;
        }
        ListNode last = reverseList03(p.next);
        // 归的时候交互相邻两个节点的次序，并让当前节点：p.next=null。
        p.next.next = p;
        p.next = null;
        return last;
    }

    // 方法4：从链表每次拿到第二个节点，将其从链表断开，插入头部，直至它为 null 结束
    private static ListNode reverseList04(ListNode o1) {
        if (o1 == null || o1.next == null) {
            return o1;
        }
        // 新头
        ListNode n1 = o1;
        // o2指向旧链表的第二个节点
        ListNode o2 = o1.next;
        while (o2 != null) {
            // 将第二个节点断开
            o1.next = o2.next;
            // o2下一个节点指向新头
            o2.next = n1;
            // n1 更新为新插入元素o2作为新头
            n1 = o2;
            // o2 从新指向旧链表的第二个节点
            o2 = o1.next;
        }
        // 返回新头
        return n1;
    }

    // 方法5：方法2的面向过程版，构造一个新头，不断从旧头移出头元素，添加到新头
    private static ListNode reverseList05(ListNode o1) {
        ListNode n1 = null;
        while (o1 != null) {
            ListNode o2 = o1.next;
            // 让新元素指向新头的下一个（否则就断开新头的连接关系了）
            o1.next = n1;
            n1 = o1;
            o1 = o2;
        }
        return n1;
    }


    private static class LinkedList {
        ListNode head;

        public LinkedList(ListNode o1) {
            this.head = o1;
        }

        public ListNode removeFirst() {
            ListNode first = this.head;
            if (first == null) {
                return null;
            }
            head = first.next;
            return first;
        }

        public void addFirst(ListNode node) {
            node.next = head;
            head = node;
        }
    }

    public static void main(String[] args) {
        ReverseList206 reverseList206 = new ReverseList206();
        ListNode n1 = ListNode.init(1, 2, 3, 4, 5);
        n1 = reverseList206.reverseList(n1);
        System.out.println(n1);
    }
}
